# 不同的子序列
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0
        dp = [0 for _ in range(len(t) + 1)]
        dp[0] = 1
        if s[0] == t[0] and len(s) >= len(t):
            dp[1] = dp[1] + 1
        for i in range(1, len(s)):
            tmp = dp.copy()
            rest = len(s) - i
            start = max(len(t) - rest, 0)
            for old in range(start, len(dp) - 1):
                if dp[old] == 0:
                    break
                if s[i] == t[old]:
                    tmp[old + 1] = dp[old + 1] + dp[old]
            dp = tmp
        return dp[-1]


if __name__ == '__main__':
    so = Solution()
    S = "aabdbaabeeadcbbdedacbbeecbabebaeeecaeabaedadcbdbcdaabebdadbbaeabdadeaabbabbecebbebcaddaacccebeaeedababedeacdeaaaeeaecbe"
    T = "bddabdcae"
    # S = "babgbag"
    # T = "bag"
    r = so.numDistinct(S, T)
    print(r)
